package leetcode每日一题;


import java.util.*;

/**
 * 1. 问题描述
 *      有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
 *      且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 *      省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 *      给你一个nxn的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，
 *      而 isConnected[i][j] = 0 表示二者不直接相连。
 *      返回矩阵中 省份 的数量。
 *
 * 2. 算法分析
 *     总体分析：
 *          我们将n个城市看成n个节点，有些节点直接有边，有的节点之间没有边，所以这个节点构成了若干
 *          互不相交的连通子图，全部的连通子图的数量就是最终求出的省份数量。
 *          所以我们的目标就是计算出到底有多少个连通子图,再次之前，我们需要知道如何求出一个图中的连
 *          通子图
 *
 *     1. DFS算法 深度优先遍历
 *          假设当前第1个城市为起始开始找到以当前城市为起点的最大连通子图，此时我们需要去遍历所有的城市
 *          如果当前遍历到的第i个城市没有被访问，且第i个城市与第1个城市相连，则我们将当前第i个城市为起
 *          点进行下一次搜索的起点城市，进行下一次dfs过程
 *          下面的代码中有详细的注释
 *
 *     2. BFS算法  广度优先遍历  非递归实现  利用队列结构
 *
 *     3. 采用并查集实现  (并查集的作用之一就是查看当前图中是否成环) (目前还不懂并查集，所以不会)
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 不同省份 {
    public static void main(String[] args) {
        int[][] isConnected = {{1,1,0},{1,1,0},{0,0,1}};
        System.out.println(findCircleNum(isConnected));
    }

    /**
     * dfs实现
     * @param isConnected
     * @return
     */
    public static int findCircleNum(int[][] isConnected) {
        int citys = isConnected.length; // 获取所有的城市数量
        int proviences = 0; // 记录所有的省份数量
        boolean[] visited = new boolean[citys]; // 判断当前城市是否被访问过
        Arrays.fill(visited,false); // 初始化为没有被访问
        for (int i = 0; i < citys; i++) { // 扫描每一个城市
            // 判断当前城市是否被访问过
            // 如果没有被访问，说明当前城市不再之前找过的任何一个连通子图中
            // 所以该城市是下一个最大连通子图的起点
            // 所以对当前城市进行dfs搜索
            if (visited[i] == false) {
                dfs(isConnected,visited,citys,i);
                proviences++; // 每次dfs找到当前图中的一个最大连通子图，即一个省份，所以自增
            }
        }
        return proviences;
    }

    /**
     * dfs算法实现
     * @param isConnected
     * @param visited
     * @param citys
     * @param cur_start
     */
    public static void dfs(int[][] isConnected,boolean[] visited,int citys,int cur_start) {
        for (int i = 0; i < citys; i++) { // 扫描所有城市
            // 如果当前城市没有被访问并且与cur_start城市相连
            // 递归调用dfs，以当前第i个城市为起点进行之后的dfs搜索
            // 注意到对于一个连通子图而言，其中所有的节点都可以看成一个
            // 所以无论我们从哪一个节点开始遍历，都会找到当前相同的最大连通子图
            // 最主要的原因：传递性，所以这样的任意性并不失一般性
            if(isConnected[cur_start][i] == 1 && visited[i] == false) {
                visited[i] = true; // 注意每访问到一个城市，我们需要及时更新该城市的访问状态
                dfs(isConnected,visited,citys,i);
            }
        }
    }

    /**
     * BFS 广度优先遍历   非递归实现
     */
    public static int findCircleNum_BFS(int[][] isConnected) {
        int citys = isConnected.length; // 所有的城市数量
        int proviences = 0; // 记录省份数量
        boolean[] visited = new boolean[citys]; // 判断当前城市是否被访问过
        Arrays.fill(visited,false); // 初始化访问数组
        Deque<Integer> deque = new LinkedList<>(); // 广度优先搜索依赖于队列这种数据结构
        for(int i = 0; i < citys; i++) { // 扫描当前每一个城市
            // 判断当前城市是否被访问过
            // 如果没有被访问过，说明当前城市不再之前找到的任何一个最大连通子图中
            if(!visited[i]) {
                // 没有被访问
                // 将当前第i个城市入队
                deque.offer(i); // 入队
                visited[i] = true;
                // 找到当前第i个城市相连的所有城市
                while(!deque.isEmpty()) {
                    int cur = deque.poll(); // 取出当前城市
                    for(int j = 0; j < citys; j++) { // 扫描所有城市
                        if(isConnected[cur][j] == 1 && !visited[j]) {
                            // 当前第j个城市访问了，所以需要修改当前第j个城市的状态
                            visited[j] = true;
                            // 相连并且没有访问过
                            deque.offer(j); // 入队
                        }
                    }
                }
                proviences++;
            }
        }
        return proviences;
    }

    /**
     * 并查集实现   并查集的作用之一就是判断图中的连通分支数量
     * 并查集的主要操作：查询和合并(合并是针对root节点而言的)
     *
     */
}
